#include <stdio.h>
#include <stdlib.h>
// 设计函数分别求两个一元多项式的乘积与和
typedef struct Polynomial
{
    int coef;  // 系数
    int index; // 指数
    struct Polynomial *next;
} Polynomial;
typedef Polynomial *Poly_ptr;

Poly_ptr ReadPoly(void);
Poly_ptr AddPoly(Poly_ptr p1, Poly_ptr p2);
Poly_ptr MultiplicationPoly(Poly_ptr p1, Poly_ptr p2);
Poly_ptr sort(Poly_ptr head);
void Print(Poly_ptr p);

int main()
{
    Poly_ptr p1, p2, pp, pm;
    p1 = ReadPoly();
    p2 = ReadPoly();
    pp = AddPoly(p1, p2);
    pm = MultiplicationPoly(p1, p2);
    Print(pm);
    Print(pp);
    return 0;
}

Poly_ptr ReadPoly(void)
{
    int n;
    scanf("%d", &n); // 将要输入n次
    Poly_ptr dummy, p;
    dummy = (Poly_ptr)malloc(sizeof(Polynomial));
    p = dummy;
    p->next = NULL;
    while (n > 0)
    {
        Poly_ptr NewNode = (Poly_ptr)malloc(sizeof(Polynomial));
        scanf("%d %d", &NewNode->coef, &NewNode->index);
        NewNode->next = NULL;
        p->next = NewNode;
        p = p->next;
        n--;
    }
    Poly_ptr head = dummy->next;
    free(dummy);
    return head;
}

Poly_ptr AddPoly(Poly_ptr p1, Poly_ptr p2)
{
    Poly_ptr dummy = (Poly_ptr)malloc(sizeof(Polynomial)); // 哑结点
    dummy->next = NULL;
    Poly_ptr p = dummy;
    while (p1 != NULL && p2 != NULL)
    {
        Poly_ptr NewNode = (Poly_ptr)malloc(sizeof(Polynomial)); // 将要接入的新节点
        NewNode->next = NULL;
        if (p1->index > p2->index) // 比较指数，判断将要执行的运算
        {
            NewNode->index = p1->index;
            NewNode->coef = p1->coef; // 结点装载
            p1 = p1->next;
            p->next = NewNode; // 链接结点
            p = p->next;       // 移动结点
        }
        else if (p1->index == p2->index)
        {
            NewNode->index = p1->index;
            NewNode->coef = (p1->coef + p2->coef); // 指数相等时，系数相加
            p1 = p1->next;
            p2 = p2->next; // 注意两个结点都要移动
            p->next = NewNode;
            p = p->next;
        }
        else
        {
            NewNode->index = p2->index;
            NewNode->coef = p2->coef;
            p2 = p2->next;
            p->next = NewNode;
            p = p->next;
        }
    }
    if (p1 != NULL)
        p->next = p1;
    else
        p->next = p2; // 连接剩下的
    Poly_ptr head = dummy->next;
    free(dummy); // 清楚哑结点
    return head;
}

Poly_ptr MultiplicationPoly(Poly_ptr p1, Poly_ptr p2)
{
    Poly_ptr dummy = (Poly_ptr)malloc(sizeof(Polynomial));
    dummy->next = NULL;
    Poly_ptr p = dummy;
    while (p1 != NULL)
    {
        while (p2 != NULL)
        {
            Poly_ptr NewNode = (Poly_ptr)malloc(sizeof(Polynomial));
            NewNode->next = NULL;
            NewNode->coef = p1->coef * p2->coef;    // 系数相乘
            NewNode->index = p1->index + p2->index; // 指数相加
            p->next = NewNode;                      // 连接新节点
            p = p->next;
            p2 = p2->next; // 移动p2
        }
        p1 = p1->next; // 移动p1
    }
    Poly_ptr head = dummy->next; // 此时head就是指向相乘过后的多项式的开头
    free(dummy);
    Poly_ptr sortedHead = sort(head);
    return sortedHead;
}
Poly_ptr sort(Poly_ptr head)
{
}
void Print(Poly_ptr p)
{
    if (p == NULL)
        printf("0 0");
    else
    {
        while (p)
        {
            printf("%d %d ", p->coef, p->index);
            p = p->next;
        }
        printf("\n");
    }
}
